package com.lxl.select;

import java.util.Arrays;

/**
 * @Classname SelectSort
 * @Description 选择排序
 * 时间复杂度 O(N^2)
 * @Date 2021/8/11 15:29
 * @Created by LXLDEMO
 */
public class SelectSort {
    public static void main(String[] args) {
        int arr[] = {2,4,3,1,6,5};

//        int arr[] = {2,4,3,1,6,5,8,1,6,66,55};
        // 普通选择排序
//        selectSort(arr,arr.length);

        // 选择排序 第一次优化
        selectSortOptimize1(arr,arr.length);

//        selectionSort2(arr);
    }

    /**
     * 选择排序
     * @param arr
     * @param len
     */
    public static void selectSort(int arr[],int len){
        int minIndex; // 记录最小元素的下标
        // 极限是倒数第二个元素
        for (int i = 0;i<len-1;i++){
            System.out.println("\n第"+(i+1)+"轮");
            minIndex = i;
            // 极限是最后一个元素
            for (int j = i+1;j<len;j++){
                if (arr[minIndex]>arr[j]){
                    minIndex = j; // 更新最小元素下标
                    System.out.println("较小元素:["+arr[minIndex]+"]； 较小元素下标:"+minIndex);
                }
            }
            // 将较小的元素放到前面 达到排序目的
            swap(arr,i,minIndex);
            System.out.println("第"+(i+1)+"次交换：" + Arrays.toString(arr));
        }
    }

    /**
     * 选择排序
     * 第一次优化
     * 找出最大最小值
     * 每轮循环都会将首尾排好
     * @param arr
     * @param len
     */
    public static void selectSortOptimize1(int arr[],int len){
        System.out.println("初始状态 " + Arrays.toString(arr));
        int minIndex = 0; // 记录较小值的下标
        int maxIndex = 0; // 记录较大值的下标
        // 极限是倒数第二个元素
        for (int i = 0;i<len/2;i++){
            System.out.println("\n第"+(i+1)+"轮");
            minIndex = i; // 本轮较小元素目标位置
            maxIndex = len-1-i; // 本轮较大元素目标位置
            // 极限是最后一个元素
            for (int j = i+1;j<len-i;j++){
                if (arr[minIndex]>arr[j]){
                    minIndex = j; // 更新较小元素下标
                }
                if (arr[maxIndex]<arr[j]){
                    maxIndex = j; // 更新较大元素下标
                }
            }
            System.out.println("较小元素:["+arr[minIndex]+"]； 较小元素下标:"+minIndex);
            System.out.println("较大元素:["+arr[maxIndex]+"]； 较大元素下标:"+maxIndex);

            swap(arr,i,minIndex); // 将较小的元素放到前面 达到排序目的
            swap(arr,len-1-i,maxIndex); // 将较大的元素放到后面 达到排序目的
            System.out.println("第"+(i+1)+"次交换：" + Arrays.toString(arr));
        }
    }




    /**
     * 每次排序找到未排序的最大和最小值，已经找过一遍的不算在内
     *
     * @param arr
     */
    public static void selectionSort2(int[] arr) {
        int minIndex, maxIndex;// 分别记录最小值下标 最大值下标
        for (int i = 0; i < arr.length / 2; i++) {
            System.out.println("\n第"+(i+1)+"轮");
            minIndex = i;
            maxIndex = i;
            for (int j = i + 1; j < arr.length - i; j++) {
                if (arr[minIndex] > arr[j]) {
                    // 循环过程中找到最小值下标
                    minIndex = j;
                }
                if (arr[maxIndex] < arr[j]) {
                    // 循环过程中找到最大值下标
                    maxIndex = j;
                }
            }
            // 将最小值提前 此条语句之后，前 i+1 个是有序的
            swap(arr,i,minIndex);

            // 如果最大值就是排序开始的时候，注意之前已经将那个位置置为了最小值，所以“最大值”的那个位置应该是之前最小值交换过去的位置
            if (maxIndex == i) {
                maxIndex = minIndex;
                System.out.println("i = " + i);
            }
            // 将数值大的向最后挪，注意i的初始值是0，
            int lastIndex = arr.length - 1 - i;
            System.out.println(arr[lastIndex] + "  " + arr[maxIndex]);
            // 交换 此条语句之后，后 i+1 个是有序的
            swap(arr,lastIndex,maxIndex);

            System.out.println("第"+(i+1)+"次交换：" + Arrays.toString(arr));

        }
    }

    /**
     * 交换函数
     * @param arr
     * @param i
     * @param j
     */
    public static void swap(int[] arr,int i ,int j){
        int temp = arr[j];
        arr[j] = arr[i];
        arr[i] = temp;
    }
}
